Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

解析

此題要求出移除Linked List從後面算起的第n個node。

解法

public ListNode removeNthFromEnd(ListNode head, int n) {
    int lastSize = n + 1;
    ListNode[] lastNodes = new ListNode[lastSize];
    int size = 0;
    ListNode node = head;
    while (node != null) {
        lastNodes[size++ % lastSize] = node;
        node = node.next;
    }
    if (n == size) return head.next;
    node = lastNodes[(size - n - 1) % lastSize];
    node.next = node.next.next;
    return head;
}    

備註

希望透過記錄解題的過程，可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知，若有更好的解法也歡迎留言，謝謝。